# 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。 
# 
#  示例 1: 
# 
#  
# 输入: temperatures = [73,74,75,71,69,72,76,73]
# 输出: [1,1,4,2,1,1,0,0]
#  
# 
#  示例 2: 
# 
#  
# 输入: temperatures = [30,40,50,60]
# 输出: [1,1,1,0]
#  
# 
#  示例 3: 
# 
#  
# 输入: temperatures = [30,60,90]
# 输出: [1,1,0] 
# 
#  
# 
#  提示： 
# 
#  
#  1 <= temperatures.length <= 105 
#  30 <= temperatures[i] <= 100 
#  
#  Related Topics 栈 数组 单调栈 
#  👍 890 👎 0
import math
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        stack = []
        for i in range(n):
            t = temperatures[i]
            while stack and temperatures[stack[-1]] < t:
                index = stack.pop()
                ans[index] = i - index
            stack.append(i)
        return ans









# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 1. 暴力
# next[] 30 - 100, 将对应位置改为气温数组中出现的位置 next[气温] = 气温数组位置
# 从后往前遍历气温数组, 从前往后遍历next数组
#     def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
#         n = len(temperatures)
#         result, next, big = [0] * n, dict(), 10 ** 9
#         for i in range(n - 1, -1, -1):
#             warmer_index = min(next.get(t, big) for t in range(temperatures[i] + 1, 102))
#             if warmer_index != big:
#                 result[i] = warmer_index - i
#             next[temperatures[i]] = i
#         return result

# 单调栈
# 栈储存下标, 栈维持栈底到栈顶递减
# 如果当前元素大于栈顶元素, 出栈, 记录结果 j - i
#     def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
#         n = len(temperatures)
#         ans = [0] * n
#         stack = []
#         for i in range(n):
#             t = temperatures[i]
#             while stack and temperatures[stack[-1]] < t:
#                 p_index = stack.pop()
#                 ans[p_index] = i - p_index
#             stack.append(i)
#         return ans

if __name__ == '__main__':
    s = Solution()
    t1 = [30, 60, 90]
    r1 = s.dailyTemperatures(t1)
    e1 = [1, 1, 0]
    t2 = [89, 62, 70, 58, 47, 47, 46, 76, 100, 70]
    r2 = s.dailyTemperatures(t2)

    assert r1 == e1, r1
